二叉树方法总结

[bosthhe1]

1，对于二叉树，我所遇到的情况必写条件if(root == NULL)下面返回内容具体情况而定 2，对于需要构建树的，或者遍历树需要把左右分开遍历的情况下，一般会有一个接受值，来接受左边和右边 3，不一定判断成功就return true ，而是视情况而定，如果需要判断树的所有节点是否相等，就需要遍历树，但是遍历树如果提前返回true就会导致后面的树遍历不了，这时候就要写反面，如果不等于就return false，如果一直遍历到空都没有false就return true，这样才能遍历每一个节点 4，同时需要注意的是，哪些问题是遍历树节点的底层节点就能拿到答案，哪些是必须遍历到底层节点的NULL节点 如求叶子节点的时候，需要将树遍历到最后一层就够了，不需要遍历底层节点下面的空节点。 5，需要注意的是，二叉树也是链表，所以将二叉树的节点对换之后，链向不同的位置，这个子树及其下面的节点都会被链过去

[bosthhe1]

1,在递归的开始，到层层递归的区间，其中的中间层都可以看作一颗颗子树，在很多oj题中，子树非常重要

2，这里面还需要细分，看做题思路，如果需要从下向上遍历，就可以直接递归到底层，如果需要从上向下遍历，就需要在中间层做一些对应的调整 对于直接递归底层的思想，比如求树的高度，需要自下至上遍历，还需要左右子树分开遍历

[bosthhe1]

一定要分清楚什么是先序，中序，后序，先序就是可以直接在递归代码上动用逻辑关系，而中序和后序则不同，中序是在第2个递归代码上动用逻辑关系，后序则是在最后才能动用逻辑关系

class Solution {
public:
    int _findTilt(TreeNode* root,int& high)
    {
        if(root==nullptr)
        return 0;
        int left = _findTilt(root->left,high);这里递归不调用逻辑关系
        int right = _findTilt(root->right,high);
        high+=abs(left-right);
        return root->val+left+right;//这里动用逻辑关系，所以是后序
    }
    int findTilt(TreeNode* root) {
        int high = 0;
        _findTilt(root,high);
        return high;
    }
};

//这里是先序代码，在第一次递归就动用逻辑关系，代码是错误的，放在这里只是为了更好的体验先序，后序的区别
class Solution {
public:
    int _findTilt(TreeNode* root,int& high)
    {
        if(root==nullptr)
        return 0;
        int left = _findTilt(root->left,high)+root->val;
        int right = _findTilt(root->right,high)+right->val;
        high+=abs(left-right);
    }
    int findTilt(TreeNode* root) {
        int high = 0;
        _findTilt(root,high);
        return high;
    }
};