代码随想录算法训练营第17天|二叉树

平衡二叉树

这种开销太大了，最好是能够在获得子树高的递归中同时判断子树是否平衡，但是我纠结的是递归的输出是布尔类型，而不是数字类型，怎么在迭代子树是否平衡时计算子树的高度呢（迭代可以计算，但是我想不通的是怎么返回）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
 
// 1.输入参数：结点
//   输出：以该结点为根节点的子树是否是平衡的
// 2.递归边界，结点为空
// 3.单层逻辑分析：
// 了解平衡二叉树：平衡二叉树的左右子树的高的差值不会超过1
// 所以在只要求左子树和右子树的高度并进行判断

var isBalanced = function(root) {
    if(!root) return true;
    //判断左右子树是否是平衡二叉树
    let flag = isBalanced(root.left) && isBalanced(root.right);
    if(!flag) return false;
    //左右子树是平衡二叉树，判断以root为根的二叉树是否平衡 
    let ldepth = gethigh(root.left);
    let rdepth = gethigh(root.right);
    console.log(ldepth,rdepth);
    if(Math.abs(ldepth - rdepth) > 1) return false;
    return true;
};

function gethigh(root){
    if(!root) return 0;
    return 1 + Math.max(gethigh(root.left), gethigh(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
27
28
29
30
31
32
33
34
35
36
37

参考了代码随想录，解决办法就是改变函数的输出，把迭代函数主体看作是计算子树高度的迭代，并在计算时顺便判断子树是否平衡，如果不平衡的话直接输出-1，平衡就正常输出子树的高数

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    return getHeight(root) === -1 ? false :true;

};

function getHeight(node){
    if(!node) return 0;
    let leftHeight = getHeight(node.left);
    if(leftHeight === -1) return -1;
    let rightHeight = getHeight(node.right);
    if(rightHeight === -1) return -1;
    if(Math.abs(leftHeight - rightHeight) > 1) return -1;
    return 1 + Math.max(leftHeight, rightHeight);
}
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

树的路径

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function(root) {
    let res = [];
    dfs(root, res, "")
    return res;
};

function dfs(node, res, str){
    str += node.val;
    if(!node.right && !node.left){//在这里判断是否是叶子结点，可以提前在为null前回溯
        res.push(str);
        return;
    }
    if(node.left) dfs(node.left, res, str + "->");
    if(node.right) dfs(node.right, res, str + "->");
}

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

404. 左叶子之和

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function(root) {
    let res = [];

    if(root.left || root.right) dfs(root, res);

    let sum = 0;
    console.log('sum:',res);
    for(item of res){
        sum += item;
    }
    return sum;
};

function dfs(node, res){
    // 叶子结点
    if(!node.left && !node.right){
        console.log(node.val);
        res.push(node.val)
        return;
    }
    // 非叶子结点
    let leftChild = node.left;
    let rightChild = node.right;
    // 如果有左孩子,都走
    if(leftChild) dfs(leftChild, res);
    // 如果有右孩子，判断右孩子是不是叶子结点
    if(rightChild){
        if(!rightChild.left && !rightChild.right){
            return;
        }else{
            // 不是叶子结点,走
            dfs(rightChild, res);
        }
        
    }
}

// 该结点是叶子结点，必须是右叶子
// 该结点不是叶子结点，那向哪个方向遍历
// 如果左孩子是叶子结点，走
//如果左孩子不是叶子结点，走
//如果右孩子是叶子结点，不走
//如果右孩子不是叶子结点，走
//综上，只需要判断右孩子是不是叶子结点

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57