树的归纳总结

发表于 | 分类于
树是一种非线性表结构，比线性表的数据结构要复杂得多。我将按照树、二叉树、二叉查找树的顺序来复习以及做相关习题，红黑树的话感觉前端似乎可以暂时不用涉及这么深？我就先不总结归纳这一部分了。

概念

树的概念

  • 有三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）
  • 节点的高度 = 节点到叶子节点的最长路径（边数）
  • 节点的深度 = 从根节点出发，到这个节点所需经历的边的个数
  • 节点的层数 = 节点的深度+1
  • 树的高度 = 根节点的高度

二叉树的概念

  • 二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。

  • 有两个比较特殊的二叉树：满二叉树、完全二叉树

  • 满二叉树：叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点
  • 完全二叉树：就是我们按顺序给二叉树的节点标号时，1，2，3，4…如果是连在一起的就是完全二叉树，如何标号成1,2,3,5这种就不是完全二叉树

树的话一般使用链式存储法，完全二叉树（其实就是堆）则是用数组存储最节省内存

二叉树的遍历

前面总结了树和二叉树的基本定义，接下来一起来看二叉树中非常重要的操作，二叉树的遍历。我将会用递归和非递归两种方式来归纳以下四种遍历方式的Javascript代码。

递归实现

1
2
3
4
5
6
7
function preOrder(root){
    if(root){
        console.log(root)
        preOrder(root.left)
        preOrder(root.right)
    }
}

非递归实现

思路：前序遍历为 根-左-右 ，主要任务就是用自己定义的栈来代替系统栈的功能。首先根节点入栈，进入while循环，如果栈不为空，则取出栈顶元素并访问，然后将栈顶元素的左右节点入栈，要注意顺序，右节点先入栈，左节点后入栈。则左节点先出栈，右节点后出栈，符合 根-左-右 的顺序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function preOrder(root){
    if(root){
        let stack = [root]      //新建栈，并将根结点root入栈            
        while(stack.length > 0){              //当栈不为空
            let topNode = stack.pop()       //取栈顶元素
            console.log(topNode)            //访问
            if(topNode.right){     //若右节点存在，入栈
                stack.push(topNode.right)
            }
            if(topNode.left){      //若左节点存在，入栈
                stack.push(topNode.left) 
            }
        }
    }
}

LeetCode对应习题144

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
    /
 Definition for a binary tree node.
 function TreeNode(val) {
     this.val = val;
     this.left = this.right = null;
 }
/
/
 @param {TreeNode} root
 @return {number[]}
*/
var preorderTraversal = function(root) {
    if(!root) return []
    let res = []
    let stack = [root]
    while(stack.length > 0){
        let node = stack.pop()
        res.push(node.val)
        if(node.right){
            stack.push(node.right)
        }
        if(node.left){
            stack.push(node.left)
        }
    }
    return res
};

递归实现

1
2
3
4
5
6
7
function inOrder(root){
    if(root){
        preOrder(root.left)
        console.log(root)
        preOrder(root.right)
    }
}

非递归实现

思路：中序遍历为 左-根-右 ，首先将游标指向根节点，然后一直向左下遍历并入栈，直到找到最左的。此时再开始回溯，如果栈不为空，则取出栈顶元素并访问，然后将游标指向当前游标位置的右节点，如果右节点为空则无操作，若不为空，则右节点（其实就类似我们最初的根节点了）入栈，并继续按照找最左的方式遍历并入栈，如此往复。直到最终栈为空，进入终态。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function inOrder(root){
    if(root){
        let stack = []
        let cursor = root                   //游标指向根节点
        while(stack.length > 0 || cursor){  

            // 在根节点的左子树遍历完后，根节点出栈并访问，游标指向根节点的右节点时，此时栈是为空的，为了防止遍历停止，
            // 加上cursor !== null 来判断此时右子树是否为空。若此时仍有右子树，则为真，可继续维持循环的进行。

            while(cursor){         //左子树存在，则入栈
                stack.push(cursor)
                cursor = cursor.left
            }
            // let node = stack.pop()      //取出栈顶元素
            // console.log(node)           //访问      
            // if(node.right){
            //     cursor = node.right
            // }

            cursor = stack.pop()
            res.push(cursor.val)
            cursor = cursor.right
            //此处两种写法都可以，但是后者似乎更直观
        }
    }
}

LeetCode对应习题94

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/
 Definition for a binary tree node.
 function TreeNode(val) {
     this.val = val;
     this.left = this.right = null;
 }
/
/
 @param {TreeNode} root
 @return {number[]}
*/
var inorderTraversal = function(root) {
    if(!root) return []
    let res = []
    let stack = []
    let cursor = root
    while(stack.length > 0 || cursor){
        while(cursor){
            stack.push(cursor)
            cursor = cursor.left
        }
        cursor = stack.pop()
        res.push(cursor.val)
        cursor = cursor.right
    }
    return res
};

递归实现

1
2
3
4
5
6
7
function postOrder(root){
    if(root){
        preOrder(root.left)
        preOrder(root.right)
        console.log(root)
    }
}

非递归实现

思路：前序遍历为 根-左-右 ，而后序遍历为 左-右-根，那么我们只需要交换前序遍历时对左右子树的遍历顺序，则变为 根-右-左，然后再逆序，则为我们需要的后序遍历 左-右-根 啦！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function postOrder(root){
    if(root){
        let stack1 = [root]     //新建栈，并将根结点root入栈
        let stack2 = []
        while(stack1.length > 0){              //当栈不为空
            let topNode = stack1.pop()       //取栈顶元素
            stack2.push(topNode)            //访问
            if(topNode.left){      //若左节点存在，入栈
                stack1.push(topNode.left) 
            }
            if(topNode.right){     //若右节点存在，入栈
                stack1.push(topNode.right)
            }
        }
        while(stack2.length > 0){
            console.log(stack2.pop())
        }
    }
}

LeetCode对应习题145

解法一 双栈法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/
 Definition for a binary tree node.
 function TreeNode(val) {
     this.val = val;
     this.left = this.right = null;
 }
/
/
 @param {TreeNode} root
 @return {number[]}
*/
var postorderTraversal = function(root) {
        if(!root) return []
        let res = []
        let stack = [root]
        while(stack.length > 0){
            let node = stack.pop()
            res.push(node.val)
            if(node.left){
                stack.push(node.left)
            }
            if(node.right){
                stack.push(node.right)
            }
        }
        return res.reverse()
};
解法二 深度优先搜索法（队列）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/
 Definition for a binary tree node.
 function TreeNode(val) {
     this.val = val;
     this.left = this.right = null;
 }
/
/
 @param {TreeNode} root
 @return {number[]}
*/
var postorderTraversal = function(root) {
if (!root) return [];
const queue = [root];
const res = [];

while (queue.length > 0) {
    const node = queue.shift();
    res.unshift(node.val);
    if (node.left) queue.unshift(node.left);
    if (node.right) queue.unshift(node.right);
}

return res;
};

其实还有一种一个栈实现的非递归方法，但是最近有好几个面试，只得加快归纳总结的速度，不能覆盖到了，以后有时间了再补回来吧～

使用队列实现

思路：队伍先进先出，首先根节点入队，然后进入while循环，若队列不为空，则队列最前端出队并访问，同时将其左右节点依次如队，若为空则无操作，输出结果则为层次遍历～
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function levelOrder(root){
    if(root){
        let queue = [root]              //新建队列，并将root入队
        while(queue.length > 0){
            let top = queue.shift()
            console.log(top)
            if(top.left){
                queue.push(top.left)
            }
            if(top.right){
                queue.push(top.right)
            }
        }
    }
}

LeetCode对应习题102

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/
 Definition for a binary tree node.
 function TreeNode(val) {
     this.val = val;
     this.left = this.right = null;
 }
/
/
 @param {TreeNode} root
 @return {number[][]}
*/
var levelOrder = function(root) {
    if(!root) return []
    let res = []
    let queue = [root]
    
    while(queue.length > 0){
        let len = queue.length
        let current = []
        for(let i = 0;i<len;i++){
            let node = queue.shift()
            current.push(node.val)
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
        res.push(current)
    }
    return res
}

配套练习题

树的解法中最好优先思考递归的方法，比较容易写。如果对访问速度有要求时，再思考非递归的方式来使用手动实现栈替代系统栈。

一、交换二叉树

解法对应于Leetcode 226 Invert Binary Tree

  • 思路：其实就是遍历树的过程，可以用深度遍历（前中后序），或者广度遍历（层次），然后将visit的操作改成交换的操作即可，交换的简便写法是使用ES6的解构赋值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if(!root) return null;
    [root.left,root.right] = [root.right,root.left];
    invertTree(root.left);
    invertTree(root.right);
    return root;
};

二、求二叉树的最大深度（按照理解我感觉这里应该叫作最大层数？）

解法对应于Leetcode 104 Maximum Depth of Binary Tree

解法一、递归法

  • 思路：从自身到左右孩子之间算上层数差1，之后就是不断递归下去。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) return 0
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1
};

解法二、BFS

  • 思路：与之前写过的层次遍历代码类似，不再赘述了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) return 0
    let res = 0
    let queue = [root]
    while(queue.length > 0){
        let len = queue.length        
        for(let i = 0;i<len;i++){
            let node = queue.shift()
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
        res += 1
    }
    return res
};

三、判断是否是二叉搜索树

解法对应于Leetcode 98 Validate Binary Search Tree

  • 思路：这个解法挺巧妙的，中序遍历二叉搜索树, 若序列递增, 则说明为二叉搜索树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
   if(!root) return true
   let stack = []
   let cursor = root
   let inorder = - Number.MAX_SAFE_INTEGER
   while(stack.length > 0 || cursor){
       while(cursor){
           stack.push(cursor)
           cursor = cursor.left
       }
       cursor = stack.pop()
       if(cursor.val <= inorder) return false
       inorder = cursor.val
       cursor = cursor.right
   }
   return true
};

四、二叉树路径和

解法对应于Leetcode 112 Path Sum

  • 思路：使用递归的方式，同时对左右子树进行遍历，每一次分叉下去，都会用Sum减掉当前节点的值，之后的节点只需要判断传进来的root是否是叶子节点以及是否等于传进来的Sum即可。这个解法非常巧妙

  • 注意事项：题目中的路径指的是根节点到叶子节点的路径，所以判断时要!root.left && !root.right来判读是否是叶子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if(!root) return false
    if(!root.left && !root.right) return root.val == sum
    return hasPathSum(root.left,sum - root.val) || hasPathSum(root.right,sum - root.val)
};